package com.lgc.algorithm.ErFenQuery;

// 二分查找是一个基础的算法，也是面试中常考的一个知识点。
// 二分查找就是将查找的键和子数组的中间键作比较，如果被查找的键小于中间键，就在左子数组继续查找；
// 如果大于中间键，就在右子数组中查找，否则中间键就是要找的元素。
public class Test1 {
    //每次移动left和right指针的时候，需要在mid的基础上+1或者-1， 防止出现死循环， 程序也就能够正确的运行。
    //
    //注意：代码中的判断条件必须是while (left <= right)，否则的话判断条件不完整，
    // 比如：array[3] = {1, 3, 5};待查找的键为5，此时在(low < high)条件下就会找不到，
    // 因为low和high相等时，指向元素5，但是此时条件不成立，没有进入while()中。
    public static void main(String args[]) {
        int[] array = new int[]{0, 1, 2, 3, 4, 5, 6, 17, 18, 29};

        Test1 test=new Test1();
        int index = test.binarySerach(array, 18);

        System.out.println(index);
    }

    /**
     * 二分查找，找到该值在数组中的下标，否则为-1
     *
     * @param array
     * @param key
     * @return
     */
    int binarySerach(int[] array, int key) {
        int left = 0;
        int right = array.length - 1;

        // 这里必须是 <=
        while (left <= right) {
            int mid = (left + right) / 2;

            if (array[mid] == key) {
                return mid;
            } else if (array[mid] < key) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
}
